package binarysearch;

/**
 * @description:
 * @author: jhy
 * @time: 2021/4/22 19:04
 */

//查找最后一个小于等于给定值的元素
public class BinarySearchDemo7 {

    public static void main(String[] args) {
        int[] nums = {1,2,2,2,4,4,4,4,4,5,6};
        int i = binarySearch(nums, 3);
        System.out.println(i);
    }

    //思路：如果nums[mid] > target，说明要查找的值在mid左边，直接right = mid - 1;
    //否则，当前仅当mid == nums.length - 1 || nums[mid+1] > target，此时mid为要找的值
    //否则，说明当前mid不是最后一个小于等于给定元素的值，需要向右查找，即left = mid + 1;
    public static int binarySearch(int[] nums,int target){

        int left = 0;
        int right = nums.length - 1;

        while (left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] > target){ //要找的值在mid左边
                right = mid - 1;
            }else {
                if(mid == nums.length - 1 || nums[mid + 1] > target){//当前mid为要找的
                    return mid;
                }
                //否则，说明当前mid不是最后一个小于等于给定元素的值，向右查找
                left = mid + 1;
            }
        }
        return -1;

    }
}
